package hot_problems_100;

import java.util.*;

public class P1_0001 {
    /*
    * 给定一个整数数组 nums 和一个整数目标值 target，
    * 请你在该数组中找出 和为目标值 target  的那 两个 整数，并返回它们的数组下标。
    * 你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。
    * 你可以按任意顺序返回答案。
    *
    * 2 <= nums.length <= 1e4
    * -1e9 <= nums[i] <= 1e9
    * -1e9 <= target <= 1e9
    * */


    public int[] twoSum(int[] nums, int target) {
        // 排序 + 二分查找 O (n log n)
        // 哈希表 O (n)
        Map<Integer, List<Integer>> map = new HashMap<>();
        for(int i=0; i<nums.length; i++){
            if(map.containsKey(nums[i])){
                map.get(nums[i]).add(i);
            } else {
                List<Integer> list = new ArrayList<>();
                list.add(i);
                map.put(nums[i], list);
            }
        }
        int[] res = new int[2];
        for(int i=0; i<nums.length; i++){
            int another_num = target - nums[i];
            if(map.containsKey(another_num)){
                if(another_num == nums[i]){
                    if(map.get(another_num).size() > 1){
                        res[0] = map.get(another_num).get(0);
                        res[1] = map.get(another_num).get(1);
                    }
                } else {
                    res[0] = map.get(another_num).get(0);
                    res[1] = map.get(nums[i]).get(0);
                }
            }
        }
        return res;
    }

}
